前言

今天的題目一樣是easy，不過我覺得很值得練習！題目在這邊：206. Reverse Linked List，是在反轉linked list。我認為對指標不熟的人可能會很頭痛XD 那就趁機來補充一點指標的概念吧！我也是這陣子才好好地搞清楚其中的關係，之前都有點半寫半背，過一陣子就忘記了，直到徹底理解了指標，這題對我而言才真的成為easy，不用去記做法就能做出來，哈哈。

ListNode class

在開始解題之前，我們不如順便來看看題目在上面給定的ListNode的class，雖然它是struct，不過class跟struct的差異只有一個預設是private，一個是public而已。
這個ListNode裡面有哪些成員呢？答案是：
1.val這個整數與
2.next這個指向ListNode型別的指標

剩下的部分都是這個class的constructor，constructor是用來確保ListNode這個類別可以被好好初始化，而寫法就是會跟class本身同名、沒有return type、有(可能是空的)參數列表與(可能是空的)函式本體。可以看到有三種建構子，代表說我們可以用ListNode()、ListNode(x)、ListNode(x, p)這幾種方式來初始化它。
而至於後面的部分，我之前對於這個寫法有點疑惑，想說一堆()(){}{}是在幹嘛，其實這個寫法是直接初始化的用法，ListNode() : val(0), next(nullptr) {}換種寫法就是

ListNode(){
    val=0;
    next=nullptr;
}

代表說如果我們丟一個空的來建立ListNode這個物件，ListNode a = new ListNode();，那a的value就會是0，而next則是nullptr。但比起這種assignment的寫法，建議還是用直接初始化的寫法會更有效率。也許之後可以再找一天討論建構子的部分XD 廢話不多說還是先進題目好了。

想法

要怎麼進行反轉呢？其實也有一種暴力作法，直接遍歷紀錄node value，存到vector裡面，再建立n個node去串回去XD 但這就比較耗空間了，我們還是直接把題目給的linked list倒過來吧！
我們可以先思考我們每次需要紀錄哪些東西。首先，需要有一個node指標是按順序去走完整個list；還要有一個指標，去保存前一個node，讓後面的node可以指回去；然後還要有一個指標擔任去把現在的node指回前一個node的角色。所以，我們需要三個指標，題目已經提供了一個head，我們可以直接拿來用，那就再兩個XD。
指向前一個node的指標我們叫它prev，因為倒過來，所以第一個prev應該是nullptr(reversed linked list的末尾)

ListNode* prev = nullptr;

然後要負責指回去的我們叫它cur好了，從第一個開始要來反轉。

ListNode* cur = head;

前置作業兩個指標初始化完畢，我們來遍歷整個linked list吧，要判斷是否抵達結尾，我們可以看是否已經指向了nullptr

while(nullptr!=head){
/*reverse*/
}

那中間的reverse要如何實做呢？
首先，我們要先讓head走到下一個位置，再來讓cur指回prev，
這個順序很重要，不然現在cur跟head是指向同一個node，如果先讓cur指標提領(dereference)出來指向prev，head的next也會變prev唷XD 就走不下去了。

head = head->next; // 改變head指向的方向，head現在指向原來的next的ListNode

head已經抵達下一個node，我們就可以實作前面反轉的部分了

cur-> next = prev; // 注意，這裡不是!!改變cur的指向，而是"提領"cur指標指向的東西，然後賦值唷!!因為cur->X會=(*cur.X)，前面*cur代表的是把cur指標指向的地方提領出來!!所以這個指標把原來那個node的next改掉了!!

接下來就讓大家keep going，下一輪的prev就是現在的cur；而下一輪的cur則是現在的head

prev = cur;
cur = head;

就這樣。沒錯，這樣就結束了！
完整程式碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // head to go through the list in order
        // 'prev' pointer keep the previous node
        ListNode* prev = nullptr;
        // cur pointer to redirect the node
        ListNode* cur = head;
        
        // go through list till the head become new pointer
        while(nullptr!=head){
            // head step to the next
            head = head->next;
            // cur node point to the prev
            cur->next = prev;
            // prev points to cur
            prev = cur;
            // update cur to the next node
            cur = head;
        }
        return prev;
    }
};

最後要return的為什麼是prev呢？因為可以看到最後一輪cur跟head都變成nullptr了！而當下的prev就是前一輪反轉後的cur囉！

結語

今天不知不覺打比較多，接下來不一定要跟著9月challenge，加一些經典的題目好了XD